package zcw.com.lib_leet_code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import zcw.com.lib_leet_code.bean.TreeNode;
import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/7/13.<br><br>
 *
 * 二叉树的所有路径
 */
public class Topic257 {

    public static void main(String[] args) {
        Topic257 instance = new Topic257();

        List<Integer> list = Arrays.asList(1,2,3,null,5);
        TreeNode root = Util.createTree(list);
        System.out.println(instance.binaryTreePaths(root));

        list = Arrays.asList(1);
        root = Util.createTree(list);
        System.out.println(instance.binaryTreePaths(root));

        list = Arrays.asList(1, 2, 3);
        root = Util.createTree(list);
        System.out.println(instance.binaryTreePaths(root));
    }

    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        StringBuilder builder = new StringBuilder();

        binaryTreePaths(root, builder, result);
        return result;
    }

    private void binaryTreePaths(TreeNode root, StringBuilder builder, List<String> result) {
        if(root == null) {
            return ;
        }

        int length = builder.length();
        if(length > 0) {
            builder.append("->");
        }
        builder.append(root.val);

        if(root.left == null && root.right == null) {
            result.add(builder.toString());
            builder.setLength(length);
            return ;
        }

        binaryTreePaths(root.left, builder, result);
        binaryTreePaths(root.right, builder, result);
        builder.setLength(length);
    }

    public List<String> binaryTreePaths2(TreeNode root) {
        List<String> result = new ArrayList<>();
        List<Integer> stack = new ArrayList<>();

        binaryTreePaths2(root, stack, result);
        return result;
    }

    private void binaryTreePaths2(TreeNode root, List<Integer> stack, List<String> result) {
        if(root == null) {
            return ;
        }

        if(root.left == null && root.right == null) {
            StringBuilder builder = new StringBuilder();
            for(int value : stack) {
                builder.append(value).append("->");
            }

            builder.append(root.val);
            result.add(builder.toString());
            return ;
        }

        stack.add(root.val);
        binaryTreePaths2(root.left, stack, result);
        binaryTreePaths2(root.right, stack, result);
        stack.remove(stack.size() - 1);
    }
}
